Search results for "Iterated local search"
showing 7 items of 7 documents
The berth allocation problem in terminals with irregular layouts
2019
As international trade thrives, terminals attempt to obtain higher revenue while coping with an increased complexity with regard to terminal management operations. One of the most prevalent problems such terminals face is the Berth Allocation Problem (BAP), which concerns allocating vessels to a set of berths and time slots while simultaneously minimizing objectives such as total stay time or total assignment cost. Complex layouts of real terminals introduce spatial constraints which limit the mooring and departure of vessels. Although significant research has been conducted regarding the BAP, these real-world restrictions have not been taken into account in a general way. The present work …
Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
2014
The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in bot…
Shaping communities of local optima by perturbation strength
2017
Recent work discovered that fitness landscapes induced by Iterated Local Search (ILS) may consist of multiple clusters, denoted as funnels or communities of local optima. Such studies exist only for perturbation operators (kicks) with low strength. We examine how different strengths of the ILS perturbation operator affect the number and size of clusters. We present an empirical study based on local optima networks from NK fitness landscapes. Our results show that a properly selected perturbation strength can help overcome the effect of ILS getting trapped in clusters of local optima. This has implications for designing effective ILS approaches in practice, where traditionally only small per…
Communities of Local Optima as Funnels in Fitness Landscapes
2016
We conduct an analysis of local optima networks extracted from fitness landscapes of the Kauffman NK model under iterated local search. Applying the Markov Cluster Algorithm for community detection to the local optima networks, we find that the landscapes consist of multiple clusters. This result complements recent findings in the literature that landscapes often decompose into multiple funnels, which increases their difficulty for iterated local search. Our results suggest that the number of clusters as well as the size of the cluster in which the global optimum is located are correlated to the search difficulty of landscapes. We conclude that clusters found by community detection in local…
An ILS-Based Metaheuristic for the Stacker Crane Problem
2012
[EN] In this paper we propose a metaheuristic algorithm for the Stacker Crane Problem. This is an NP-hard arc routing problem whose name derives from the practical problem of operating a crane. Here we present a formulation and a lower bound for this problem and propose a metaheuristic algorithm based on the combination of a Multi-start and an Iterated Local Search procedures. Computational results on a large set of instances are presented.
Determining the Difficulty of Landscapes by PageRank Centrality in Local Optima Networks
2016
The contribution of this study is twofold: First, we show that we can predict the performance of Iterated Local Search (ILS) in different landscapes with the help of Local Optima Networks (LONs) with escape edges. As a predictor, we use the PageRank Centrality of the global optimum. Escape edges can be extracted with lower effort than the edges used in a previous study. Second, we show that the PageRank vector of a LON can be used to predict the solution quality (average fitness) achievable by ILS in different landscapes.
The collaborative consistent vehicle routing problem with workload balance
2021
Abstract The rising competition in the logistics sector forces companies to be more economically efficient. One of the major sources of inefficiency is the incomplete usage of available resources, such as vehicles’ capacities. Mechanism that allow to better exploit such resources by enabling carrier collaborations are on the rise. Our study examines a centrally organized multi-period collaborative vehicle routing problem, where carriers can exchange customers who have to be serviced on a regular basis. Collaborations, where carriers serve frequent customers, are supposed to face the problem of (i) time consistency in terms of visiting time, and of (ii) service consistency. The latter ensure…